#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono> // 包含时间测量头文件
#include <numeric> // 包含 accumulate 函数所需的头文件

using namespace std;

// 时间测量函数
template<typename F>
auto measure_time(const F& func) -> decltype(func()) {
    auto start = chrono::high_resolution_clock::now();
    auto result = func();
    auto end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::microseconds>(end - start).count(); // 使用微秒级别的精度
    cout << "Execution time: " << duration << " μs" <<endl ;
    return result;
}

// 平凡算法（暴力递归）
int banknoteChangeNaive(vector<int>& banknotes, int amount, vector<int>& banknoteCount, vector<int>& bestBanknoteCount, int currentCount, int& currentMin) {
    if (amount == 0) {
        if (currentCount < currentMin) {
            currentMin = currentCount;
            bestBanknoteCount = banknoteCount;
        }
        return 0;
    }
    if (amount < 0 || currentCount >= currentMin) return -1;

    int minBanknotes = INT_MAX;
    for (int i = 0; i < banknotes.size(); ++i) {
        banknoteCount[i]++;
        int subResult = banknoteChangeNaive(banknotes, amount - banknotes[i], banknoteCount, bestBanknoteCount, currentCount + 1, currentMin);
        banknoteCount[i]--;
        if (subResult != -1) {
            minBanknotes = min(minBanknotes, subResult + 1);
        }
    }

    return (minBanknotes == INT_MAX) ? -1 : minBanknotes;
}

pair<int, vector<int>> banknoteChangeNaive(vector<int>& banknotes, int amount) {
    vector<int> banknoteCount(banknotes.size(), 0);
    vector<int> bestBanknotesCount(banknotes.size(), 0);
    int currentMin = INT_MAX;
    int minBanknotes = banknoteChangeNaive(banknotes, amount, banknoteCount, bestBanknotesCount, 0, currentMin);
    return { minBanknotes, bestBanknotesCount };
}
// 动态规划优化算法（使用记忆体）
int banknoteChangeDPHelper(vector<int>& banknotes, int amount, vector<int>& memo, vector<vector<int>>& banknoteCounts) {
    if (amount == 0) return 0;
    if (amount < 0) return -1;
    if (memo[amount] != -1) return memo[amount];

    int minBanknotes = INT_MAX;
    int banknoteIndex = -1;
    for (int i = 0; i < banknotes.size(); ++i) {
        int banknote = banknotes[i];
        int subResult = banknoteChangeDPHelper(banknotes, amount - banknote, memo, banknoteCounts);
        if (subResult >= 0 && subResult < minBanknotes) {
            minBanknotes = subResult + 1;
            banknoteIndex = i;
        }
    }

    memo[amount] = (minBanknotes == INT_MAX) ? -1 : minBanknotes;

    if (banknoteIndex != -1) {
        banknoteCounts[amount] = banknoteCounts[amount - banknotes[banknoteIndex]];
        banknoteCounts[amount][banknoteIndex]++;
    }

    return memo[amount];
}

pair<int, vector<int>> banknoteChangeDP(vector<int>& banknotes, int amount) {
    vector<int> memo(amount + 1, -1);
    vector<vector<int>> banknoteCounts(amount + 1, vector<int>(banknotes.size(), 0));
    int minBanknotes = banknoteChangeDPHelper(banknotes, amount, memo, banknoteCounts);

    return { minBanknotes, banknoteCounts[amount] };
}

// 贪心算法
pair<int, vector<int>> banknoteChangeGreedy(vector<int>& banknotes, int amount) {
    int n = banknotes.size();
    vector<int> banknoteCounts(n, 0); // 存储每种硬币的数量
    int minBanknotes = 0; // 最少硬币数量

    for (int i = n - 1; i >= 0; --i) {
        while (amount >= banknotes[i]) {
            amount -= banknotes[i];
            banknoteCounts[i]++;
            minBanknotes++;
        }
    }

    // 如果无法凑出指定金额，返回-1
    if (amount > 0) minBanknotes = -1;

    return { minBanknotes, banknoteCounts };
}

int main() {
    vector<int> banknotes = { 10, 50, 100 }; // 假设可用的纸币面值为 10, 50, 100  

    int amount;
    cout << "Enter the amount to withdraw: ";
    cin >> amount;
    cout << endl;
    if (amount <= 0) {
        cout << "Invalid amount entered. Please enter a positive amount." << endl;
        return 1;
    }

    // 测量平凡算法的执行时间  
    auto resultNaive = measure_time([&]() {
        return banknoteChangeNaive(banknotes, amount);
        });

    if (resultNaive.first == -1)
    {
        cout << "Invalid amount entered. Please enter a valid amount." << endl;
        return 1;
    }

    cout << "Minimum number of banknotes needed (Naive) for amount " << amount << " is " << resultNaive.first << endl;
    cout << "banknote usage (Naive): " << endl;
    for (int i = banknotes.size() - 1; i >= 0; --i) {
        cout << banknotes[i] << "￥: " << resultNaive.second[i] << " pieces" << endl;
    }
    cout << endl << endl;

    // 测量动态规划算法的执行时间  
    auto resultDP = measure_time([&]() {
        return banknoteChangeDP(banknotes, amount);
        });
    cout << "Minimum number of banknotes needed (DP) for amount " << amount << " is " << resultDP.first << endl;
    cout << "banknote usage (DP): " << endl;
    for (int i = banknotes.size() - 1; i >= 0; --i) {
        cout << banknotes[i] << "￥: " << resultDP.second[i] << " pieces" << endl;
    }
    cout << endl << endl;

    // 测量贪心算法的执行时间
    auto resultGreedy = measure_time([&]()
        {
            return banknoteChangeGreedy(banknotes, amount);
        });
    cout << "Minimum number of banknotes needed (Greedy) for amount " << amount << " is " << resultGreedy.first << endl;
    cout << "banknote usage (Greedy): " << endl;
    for (int i = banknotes.size() - 1; i >= 0; --i) {
        cout << banknotes[i] << "￥: " << resultGreedy.second[i] << " pieces" << endl;
    }
    cout << endl;

    return 0;
}
